package sorting;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class QuickSort {
	static int divide(Integer[] a, int low, int high) {
		int i = low - 1, j;
		int key = a[high];
		for (j = low; j < high;/* j++ */) {
			if (a[j] > key)
				j++;
			else {
				i++;
				int temp = a[i];
				a[i] = a[j];
				a[j] = temp;
				j++;
			}
		}
		i++;
		int temp = a[i];
		a[i] = a[high];
		a[high] = temp;
		return i;
	}

	static int select(Integer[] a, int low, int high, int k) {
		int p = divide(a, low, high);
		if (p > k)
			return select(a, low, p - 1, k);
		else if (p < k)
			return select(a, p + 1, high, k - p);
		else
			return a[p];
	}

	static void sort(Integer[] a, int low, int high) {
		if (low < high) {
			int p = divide(a, low, high);
			sort(a, low, p - 1);
			sort(a, p + 1, high);
		}
	}

	public static void main(String[] args) {
		int size = 10;
		Random rand = new Random();
		Integer[] a = new Integer[size];
		for (int i = 0; i < size; i++)
			a[i] = i;
		// Arrays.sort(a);
		List<Integer> lists = Arrays.asList(a);
		System.out.println(lists);
		Collections.reverse(lists);
		System.out.println(lists);
		Collections.shuffle(lists, rand);
		Integer[] b = lists.toArray(new Integer[] {});
		System.out.println(Arrays.toString(b));
		// divide(b, 0, size - 1);
		sort(b, 0, size - 1);
		System.out.println(Arrays.toString(b));
		System.out.println(select(b, 0, size - 1, 6));
	}
}
